package ink.lvxin.datastructure.ch3;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 *
 * @author LvXin
 */
public class StackTest {

    private static final Character LEFT_BRACKETS = '(';
    private static final Character RIGHT_BRACKETS = ')';

    public static void main(String[] args) {
        String infix = "a + b * c + (d * e + f ) * g ";

        System.out.println(getPostfix(infix));
    }

    /**
     * 中缀表达式 转为 后缀表达式
     * @param infix
     * @return
     */
    private static String getPostfix(String infix) {

        StringBuilder sb = new StringBuilder();
        Map<Character, Integer> priorityMap = new HashMap<>();
        priorityMap.put('+', 10);
        priorityMap.put('*', 20);

        Stack<Character> stack = new Stack<>();

        for (Character c : infix.toCharArray()) {
            if (c == ' ') {
                continue;
            }

            if (LEFT_BRACKETS.equals(c)) {
                stack.push(c);
                continue;
            }

            if (RIGHT_BRACKETS.equals(c)) {
                popOper(sb,stack);
                char current = stack.peek();
                if (current == LEFT_BRACKETS) {
                    stack.pop();
                }
                continue;
            }

            Integer priority = priorityMap.get(c);
            if (priority == null) {
                sb.append(c);
                continue;
            } else {
                if (stack.isEmpty()) {
                    stack.push(c);
                    continue;
                }

                while (true) {
                    if (stack.isEmpty()) {
                        break;
                    }
                    char lastStack = stack.peek();

                    if (LEFT_BRACKETS == lastStack) {
                        break;
                    }

                    Integer priority2 = priorityMap.get(lastStack);
                    if (priority2 < priority) {
                        break;
                    }

                    sb.append(stack.pop());
                }

                stack.push(c);
                continue;

            }
        }

        popAll(sb, stack);

        return sb.toString();
    }

    private static void popAll(StringBuilder sb, Stack<Character> stack) {
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
    }

    private static void popOper(StringBuilder sb, Stack<Character> stack) {
        for (; ; ) {
            if (stack.isEmpty()) {
                break;
            }

            char top = stack.peek();
            if (top == LEFT_BRACKETS) {
                break;
            }
            sb.append(stack.pop());

        }
    }
}
